package LC_plus;

/**
 * 将单向链表按某值划分成左边小，中间相等，右边大的形式
 * 思路：使用3个指针，把原链表依次划分成三个部分的链表，然后再把他们合并起来，空间复杂度为 O(1), 而且内部节点的顺序也是和原链表一致。
 * 参考 LeetCode 86 题
 */
public class 分割链表三 {
    public ListNode partition(ListNode head, int x) {
        ListNode p1 = new ListNode(-1);
        ListNode p2 = new ListNode(-1);
        ListNode p3 = new ListNode(-1);
        ListNode cur1 = p1;
        ListNode cur2 = p2;
        ListNode cur3 = p3;
        ListNode cur = head;
        while (cur != null) {
            if (cur.val < x) {
                cur1.next = cur;
                cur1 = cur1.next;
            } else if (cur.val == x) {
                cur2.next = cur;
                cur2 = cur2.next;
            } else {
                cur3.next = cur;
                cur3 = cur3.next;
            }
            cur = cur.next;
        }

        if (p2.next != null) {
            cur1.next = p2.next;
            if (p3.next != null) {
                cur2.next = p3.next;
                cur3.next = null;
            } else {
                cur2.next = null;
            }
        } else if (p3.next != null) {
            cur1.next = p3.next;
            cur3.next = null;
        } else {
            cur1.next = null;
        }

        return p1.next;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(9);
        ListNode t2 = new ListNode(0);
        ListNode t3 = new ListNode(4);
        ListNode t4 = new ListNode(5);
        ListNode t5 = new ListNode(3);
        head.next = t2;
        t2.next = t3;
        t3.next = t4;
        t4.next = t5;
        分割链表三 t = new 分割链表三();
        ListNode res = t.partition(head, 4);
        while (res != null) {
            System.out.println(res.val);
            res = res.next;
        }
    }
}
